package main

import (
	"fmt"
	"math/rand"
)

const p = 0.35
const MAXLEVEL = 32

type Skiplist struct {
	Level int
	Head  *Node
}

type Node struct {
	Key      int
	Forwards []*Node
}

func randLevel() int {
	level := 1
	for rand.Float64() < p && level < MaxLevel {
		level++
	}
	return level
}

func (s *Skiplist) Search(key int) bool {
	x := s.Head
	for i := s.Level - 1; i >= 0; i-- {
		for x.Forwards[i] != nil && x.Forwards[i].Key < key {
			x = x.Forwards[i]
		}
	}

	x = x.Forwards[0]
	if x != nil && x.Key == key {
		return true
	} else {
		return false
	}

}

func (s *Skiplist) Insert(key int) {
	x := s.Head
	update := make([]*Node, MAXLEVEL)
	for i := s.Level - 1; i >= 0; i-- {
		for x.Forwards[i] != nil && x.Forwards[i].Key < key {
			x = x.Forwards[i]
		}
		update[i] = x
	}

	x = x.Forwards[0]
	if x != nil && x.Key == key {
		return
	}

	node := &Node{
		Key:      key,
		Forwards: make([]*Node, MAXLEVEL),
	}

	level := randLevel()

	if level > s.Level {
		for i := s.Level; i < level; i++ {
			update[i] = s.Head
		}
		s.Level = level
	}

	for i := s.Level - 1; i >= 0; i-- {
		node.Forwards[i] = update[i].Forwards[i]
		update[i].Forwards[i] = node
	}

	return
}

func (s *Skiplist) Delete(key int) {
	x := s.Head
	for i := s.Level - 1; i >= 0; i-- {
		for x.Forwards[i] != nil {
			if x.Forwards[i].Key == key {
				tmp := x.Forwards[i]
				x.Forwards[i] = tmp.Forwards[i]
				tmp.Forwards[i] = nil
			} else if x.Forwards[i].Key > key {
				break
			} else {
				x = x.Forwards[i]
			}
		}
	}
}

func main() {
	list := newSkipList()
	for i := 0; i < 20; i++ {
		list.insert(rand.Intn(100))
	}
	list.print()

	fmt.Println("\n--------------------------------------")

	list.delete(10)
	list.print()

	fmt.Println("\n--------------------------------------")
}
